package com.zhugang.week13.linkedlist;

/**
 * @program algorithms
 * @description: addTwoNumbers
 * @author: chanzhugang
 * @create: 2022/10/23 21:52
 */
public class AddTwoNumbers {


    /**
     * 2 两数相加
     * https://leetcode.cn/problems/add-two-numbers/
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 链表上的两数相加：注意进位
        // newNode + tail ; 和与10操作：余数作为尾节点，除数作为进一位
        ListNode newNode = new ListNode();
        ListNode tail = newNode;
        ListNode p = l1;
        ListNode q = l2;
        // 进一位
        int carry = 0;
        while (p != null || q != null || carry != 0) {
            int sum = 0;
            if (p != null) {
                sum += p.val;
                p = p.next;
            }
            if (q != null) {
                sum += q.val;
                q = q.next;
            }
            if (carry != 0) {
                // 进位
                sum += carry;
            }
            // 余数
            ListNode node = new ListNode(sum % 10);
            // 除数：进一位
            carry = sum / 10;
            tail.next = node;
            tail = node;
        }
        /*if (carry != 0) {
            tail.next = new ListNode(carry);
        }*/
        return newNode.next;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}